package edu.kmust.simple;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author： 常伟
 * @create： 2019/02/26 14:09
 * @email： kmustchang@qq.com
 * @version: 1.0
 * @Description： 第一题：狼羊菜过河问题
 *      一个人在河边，带着一匹狼、一只羊和一颗卷心菜。他需要用船将这三样东西运至对岸，然而，这艘船的空间有限，只容得下他自己和
 *      另一样东西（或狼或羊或卷心菜）。若他不在场看管的话，狼就回去吃羊，羊就回去吃卷心菜。此人如何才能把这三个“乘客”都运至
 *      对岸。
 */
public class ExaminationOne02 {

    /**
     * 这个表示终止状态（结束状态）
     */
    private static final int END_STATE=15;

    /**
     * 这个表示最初状态（开始状态）
     */
    private static final int BGEIN_STATE=0;

    /**
     * 这个表示结果
     */
    private List<List<String>> result=new ArrayList<>();

    /**
     * 这个表示从开始状态到目前的序列，这个序列还有一个作用，就是用于避免重复。
     * 避免将重复的状态加入进来。
     */
    private List<String> path=new ArrayList<>();

    /**
     * 用来表示当前的状态，
     *      0表示人
     *      1表示狼
     *      2表示羊
     *      3表示卷心菜
     *      因为船始终和人在一起，所以就将船和人用一个来表示
     *      value   
     *              0表示在河岸
     *              1表示在河对岸
     *      即state[0]=0就表示人在河岸，state[2]=1表示羊在河对岸。
     */
    private int[] position=new int[4];

    /**
     * 用于表示16种状态，用于表示某一种状态是都在状态空间图中出现过。
     */
    private int[] state = new int[END_STATE+1];
    
    public static void main(String[] args) {
        ExaminationOne02 examinationOne02=new ExaminationOne02();
        examinationOne02.compute();
        System.out.println(examinationOne02.result);
    }

    public void compute(){
        init();
        computeResult();
    }

    /**
     * 用于完成计算的初始化任务
     */
    public void init(){
        state[BGEIN_STATE]=1;
        path.add(path(position));
    }

    public void computeResult(){
        //如果进行到了最终的结果，就将结果加入到最终的结果中
        if(completeIndex(position)==END_STATE){
            result.add(new ArrayList<>(path));
            path.remove(path.size()-1);
            state[END_STATE]=0;
        }else{
            //遍历所有的移动情况，现在不管这个操作是不是可以进行，也不管这个操作是否合法。
            for(int i=0;i<position.length;i++){
                //只有这个操作可以进行才进行操作，只有单独移动人或者这个人与某一个动物在同一个河边。如果人和某一个动物不在一个河边，则不能进行这个操作。
                if(i==0 || position[i]==position[0]){
                    //对人或者动物进行移动位置
                    position[0]=1-position[0];
                    if(i!=0){
                        position[i]=position[0];
                    }
                    //验证这次移动是都合法。
                    if(validate()){
                        path.add(path(position));
                        state[completeIndex(position)]=1;
                        computeResult();
                    }
                    position[0]=1-position[0];
                    if(i!=0){
                        position[i]=position[0];
                    }
                }
            }
            path.remove(path.size()-1);
            state[completeIndex(position)]=0;
        }
    }

    /**
     * 这个方法的作用：
     *                  用于判断状态是不是合法，有没有违反约束条件。
     *                  如果违反约束条件就返回：false
     *                  如果没有违反约束条件就返回：true
     * @return
     */
    public boolean validate(){
        if(state[completeIndex(position)]==1){
            return false;
        }
        if((position[1]==position[2] || position[2]==position[3]) && position[2]!=position[0]){
            return false;
        }
        return true;
    }

    /**
     * 这个方法的作用：
     *                  就是从当前状态获取到唯一确定的值。
     *                  我们的计算方法是：currentState[0]*2^0+currentState[1]*2^1+currentState[2]*2^2+currentState[3]*2^3
     *                  也就是计算二进制数的currentState的十进制数。
     *                  即0000---》1111，从0到15，一共16重状态
     * @param currentState
     * @return
     */
    public int completeIndex(int[] currentState){
        return IntStream.range(0,currentState.length).map(i->currentState[i]*(1<<i)).sum();
    }

    /**
     * 获得某一个数组，从最小下标到最大下标中所有数组连接起来的字符串
     * @param position
     * @return
     */
    public String path(int[] position){
        return Arrays.stream(position).mapToObj(Integer::toString).collect(Collectors.joining());
    }
}
